'''
https://leetcode.cn/problems/number-of-islands/
'''

from typing import List

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0]) # 网格的边界，防止越界
        ans = 0

        def dfs(i, j): # i,j 是当前岛屿的起点坐标
            '''
            把相邻的1全部变成0，（不包含斜方向）
            意义：
            把已经找到的岛屿去掉，
            防止重复寻找
            '''
            if 0 <= i < m and 0 <= j < n and grid[i][j] == '1':
                grid[i][j] = '0'
                dfs(i + 1, j) # 向下
                dfs(i - 1, j) # 向上
                dfs(i, j + 1) # 向右
                dfs(i, j - 1) # 向左

        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    ans += 1 # 找到了一个岛屿 就统计一次
                    '''统计过了，就把这个岛屿从地图上抹去，防止重复计数'''
                    dfs(i, j)
        return ans










